package com.mlh.sort;

import java.lang.reflect.Array;
import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = {53, 17, 78, 9, 45, 65, 87, 32, 345, 7, 67, 1, 1, 1, 1, 1, 1, 1, 45, 6, 7, 8, 5, 3, -3};
		method1(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}

	public static void method1(int[]arr,int begin,int end){
		if(begin>=end){
			return;
		}
		int mid=(begin+end)/2;
		method1(arr,begin,mid);
		method1(arr,mid+1,end);
		//需要消耗额外的数组来帮助归并的过程
		int[] temp=new int[arr.length];
		for(int i=begin;i<=end;i++){
			temp[i]=arr[i];
		}
		int a=begin,b=mid+1;
		while(a<=mid&&b<=end){
			if(temp[a]>temp[b]){
				arr[begin]=temp[b];
				b++;
			}else{
				arr[begin]=temp[a];
				a++;
			}
			begin++;
		}
		if(a>mid){
			while(b<=end){
				arr[begin]=temp[b];
				b++;
				begin++;
			}
		}else{
			while (a<=mid){
				arr[begin]=temp[a];
				a++;
				begin++;
			}
		}
	}
}
